package treeedit;

import java.util.Random;
import java.util.Stack;

public class RandomTreeGenerator {
	/**
	 * Return a random tree with given parameters.
	 * 
	 * @param layers
	 *            number of layers (generations) of tree nodes
	 * @param fanout
	 *            number of children for each node
	 * @param labelLength
	 *            length of text labels given to each node
	 * @return full tree with @layers layers, each node having @fanout children
	 *         and @labelLength long name
	 */
	public static Tree getFullRandomTree(int layers, int fanout, int labelLength) {
		if (layers < 1)
			return null;

		// Random r = new Random(System.currentTimeMillis());
		Tree root = new Tree(getRandomString(labelLength));

		if (layers == 1)
			return root;

		// stack of nodes to add children to
		Stack<Tree> leaves = new Stack<Tree>();
		leaves.push(root);

		Tree act;
		// while we have nodes which need children
		while (!leaves.isEmpty()) {
			act = leaves.pop();
			for (int i = 0; i < fanout; i++) {
				act.addChild(getFullRandomTree(layers - 1, fanout, labelLength));
			}
		}
		return root;
	}

	/**
	 * Randomly removes some nodes from a given tree.
	 * 
	 * @param root
	 *            root of a tree to be randomized
	 * @param chanceToRemove
	 *            chance for each node to be removed - in %. Root cannot be
	 *            removed.
	 * @return randomized tree
	 */
	public static Tree randomizeTree(Tree root, int chanceToRemove) {
		if (chanceToRemove <= 0 || root == null || root.getLeavesSize() == 1)
			return root;

		Random r = new Random();

		Stack<Tree> toRemove = new Stack<Tree>();

		// every child can be removed
		for (Tree child : root.getChildren()) {
			if (r.nextInt(100) < chanceToRemove) {
				// delete or rename?
				if (r.nextBoolean()) {
					// delete, mhwahwahwa
					toRemove.push(child);
				} else {
					// just rename
					child.setName(getRandomString(child.getName()));
				}
			}
		}

		// remove the unlucky ones
		while (!toRemove.isEmpty()) {
			Tree sadChild = toRemove.pop();
			sadChild.removeThis(root);
		}

		// every child will have its children randomized
		for (Tree child : root.getChildren()) {
			randomizeTree(child, chanceToRemove);
		}

		return root;
	}

	/**
	 * Get random string composed of capital letters of given length
	 * 
	 * @param length
	 *            number of letters in the resulting string
	 * @return random string of letters
	 */
	public static String getRandomString(int length) {
		Random r = new Random();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < length; i++) {
			sb.append((char) (65 + r.nextInt(26)));
		}
		return sb.toString();
	}

	/**
	 * Get random string composed of capital letters of the same length as
	 * provided string
	 * 
	 * @param length
	 *            number of letters in the resulting string
	 * @return random string of letters
	 */
	public static String getRandomString(String string) {
		return getRandomString(string.length());
	}

	/**
	 * Generate depth or flat tree
	 * 
	 * @param numberOfNodes
	 *            : Number of nodes of the tree we want to generate.
	 * @param type
	 *            : depth or flat tree
	 * @param tolerance
	 *            : +/- number of nodes which can be acceptable.
	 * @return A randomly generated tree with @numberOfNodes +/- @tolerance
	 *         nodes. The @type signifies, what will the resulting node look
	 *         like.
	 */
	public static Tree generateDeepOrFlatTree(int numberOfNodes, String type,
			int tolerance) {
		int a_layers = 0;
		int n_fanout = 2;
		int size = 0;
		Tree tree = null;
		try {
			if (type.equals("depth")) {
				for (int a = 2; a < 10; a++) {
					for (int n = 5; n < 20; n++) {
						size = 1;
						for (int i = 0; i < a; i++) {
							size += (int) Math.pow(n, i);
						}
						if (Math.abs(size - numberOfNodes) < tolerance) {
							// System.out.println(String.format(
							// "a= %s; n= %s; result = %s", a, n, size));
							a_layers = a;
							n_fanout = n;

						}
					}
				}
				tree = RandomTreeGenerator.getFullRandomTree(a_layers, n_fanout, 3);
			} else if (type.equals("flat")) {
				for (int a = 5; a < 20; a++) {
					for (int n = 2; n < 10; n++) {
						size = 1;
						for (int i = 0; i < a; i++) {
							size += (int) Math.pow(n, i);
						}
						if (Math.abs(size - numberOfNodes) < tolerance) {
							// System.out.println(String.format(
							// "a= %s; n= %s; result = %s", a, n, size));
							a_layers = a;
							n_fanout = n;
						}
					}
				}
				tree = RandomTreeGenerator.getFullRandomTree(a_layers, n_fanout, 3);
			}
			return tree;
		} catch (NullPointerException ex) {
			System.out.println("Not found any match result");
			return null;
		}
	}
}
